package 剑指offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Offer38_JZ27 {
    static ArrayList<String> result = new ArrayList<>();
    static Set<String> set = new HashSet<>();
    public static ArrayList<String> Permutation(String str) {
        boolean[] used = new boolean[str.length()];
        backtrack(str.toCharArray(), new StringBuilder(), used);
        return result;
    }

    public static void backtrack(char[] chars, StringBuilder stringBuilder, boolean[] used) {
        if (stringBuilder.length() == chars.length && !set.contains(stringBuilder.toString())) {
            result.add(stringBuilder.toString());
            set.add(stringBuilder.toString());
            return;
        }

        for (int i=0; i<chars.length; i++) {
            if (used[i]) {
                continue;
            }
            stringBuilder.append(chars[i]);
            used[i] = true;
            backtrack(chars, stringBuilder, used);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        System.out.println(Permutation("abca").toString());
    }
}
